package me.mingshan.leetcode;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/duplicate-zeros/description/
 * <p>
 * <p>
 * 给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
 * <p>
 * 注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：arr = [1,0,2,3,0,4,5,0]
 * 输出：[1,0,0,2,3,0,0,4]
 * 解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]
 * 示例 2：
 * <p>
 * 输入：arr = [1,2,3]
 * 输出：[1,2,3]
 * 解释：调用函数后，输入的数组将被修改为：[1,2,3]
 *
 * @author hanjuntao
 * @date 2025/6/27 0027
 */
public class UL_1089_duplicate_zeros {

    public static void main(String[] args) {
        // 1,0,2,3,0,4,5,0  指向1位置
        // 1,0,0,2,3,0,4,5  指向1位置
        // 1,0,0,2,3,0,0,4

        int[] arr = {1, 0, 2, 3, 0, 4, 5, 0};
       // duplicateZeros3(arr);
        // [1, 0, 0, 2, 3, 0, 0, 4]
     //   System.out.println(Arrays.toString(arr));

        int[] arr2 = {8,4,5,0,0,0,0,7};
        duplicateZeros3(arr2);
        // [8, 4, 5, 0, 0, 0, 0, 0]
        System.out.println(Arrays.toString(arr2));

        int[] arr3 = {1, 0, 2, 0, 0, 4, 5, 0};
      //  duplicateZeros3(arr3);
        // [1, 0, 0, 2, 0, 0, 0, 0]
       // System.out.println(Arrays.toString(arr3));


        // 1,0,2,3,0,4,5,0  r指向7位置，l 指向5位置
        // 1,0,2,3,0,4,5,4  r指向6位置，l 指向4位置
        // 1,0,2,3,0,0,0,4  r指向4位置, l 指向3位置

        // 8,4,5,0,0,0,0,7  r指向7位置，l 指向3位置
        // 8,4,5,0,0,0,0,0  r指向5位置，l 指向2位置
        // 8,4,5,0,0,0,0,0
    }

    /**
     * 思路：暴力处理
     *
     * 当前位置i检测到0时：
     * 1. 将[i+1, n-2]的数移动到[i+2, n-1]
     * 2. i+1位置设置0
     * 3。循环跳过下一个
     *
     * @param arr
     */
    public static void duplicateZeros(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 0 && i < n - 1) {
                // 将[i+1, n-2]的数移动到[i+2, n-1]
                // i+1位置设置0
                // 从后往前处理
                // 将前一位的值赋给后一位
                for (int j = n - 1; j >= i + 2; j--) {
                    arr[j] = arr[j - 1];
                }

                arr[i + 1] = 0;
                // 跳过i+1位置
                i++;
            }
        }
    }

    /**
     * 思路：
     * 1. 先统计0的个数（最后一个0不做统计）
     * 2. 倒序遍历数组，将数字移动到正确的位置
     *
     * 定义两个指针,r l
     * r 指向最后一位待放置的元素
     * l 指向最后一位待读取的元素
     *
     *
     * 实现的不对
     *
     *
     *
     * https://leetcode.cn/problems/duplicate-zeros/solutions/1606870/c-by-xiaohu9527-71ld/
     *
     * @param arr
     */
    public static void duplicateZeros2(int[] arr) {
        // 统计0的个数，不包含最后一位0
        int zeroCount = 0;

        // 我相信很多人肯定第一想法是直接记录该数组中原本有多少0，但是实际上不应该为这样。
        // 因为在数组后面的0也可以被当成普通元素被舍弃掉，因此不会有复制的逻辑。
        // 因此正确的做法为，从左右两侧开始用双指针记录，左边每碰到一个0，后边就舍弃一个元素。
        // 一直到左边指针大于右边指针的时候，我们才停止检测有多少个0需要被复制。即i > j
        //
        //作者：小虎
        //链接：https://leetcode.cn/problems/duplicate-zeros/solutions/1606870/c-by-xiaohu9527-71ld/
        //来源：力扣（LeetCode）
        //著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

        int l1 = 0, r1 = arr.length - 1;

        while (l1 < r1) {
            if (arr[l1] == 0) {
                zeroCount++;
                r1--;
            }
            l1++;
        }

        int r = arr.length - 1;
        int l = arr.length - 1 - zeroCount;

        // 需要统计处理过多少0
        // 如果都处理完了，自然退出

        while (l >= 0 && l < r) {
            // 如果l位置不是0，则将l位置的元素赋给r位置
            // 同时l减1, r减1
            if (arr[l] != 0) {
                arr[r] = arr[l];
                r--;
                l--;
            } else {
                // 如果l位置是0
                // r的位置赋0
                // r -1的位置也赋0

                // r需要减2
                // l需要减1
                arr[r] = 0;
                arr[r - 1] = 0;
                r -= 2;
                l--;
            }
        }
    }

    public static void duplicateZeros3(int[] arr) {

        // i: 用于从左边遍历元素，如果碰到0时则需要将j减去1表示舍弃一个元素为复制0腾出空间。
        // j：用于从数组尾部开始，即右边，指向下一个即将被抛弃的元素。
        // k：用于从后往前复制需要保留的元素时，指向下一个被复制元素需要去的位置。
        //

        int n = arr.length, i, j = n-1, k = n-1;
        for(i = 0; i < j; ++i) {
            if(arr[i] == 0) {
                --j;
            }
        }

        // 此处特判需要读者多加思考
        if(i == j && arr[i] == 0) {
            arr[k--] = arr[j--];
        }

        while(j >= 0) {
            if(arr[j] == 0) {
                arr[k--] = 0;
            }
            arr[k--] = arr[j--];
        }
    }
}
